package twice.class_digui;

import java.util.concurrent.ForkJoinPool;

//最接近的累加和
public class Class20_SplitSumClosed {
    public static int getSum(int[] arr){
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return process(arr, 0, sum / 2);
    }
    public static int process(int[] arr,int index,int rest){
        if(index == arr.length){
            return 0;
        }
        int p1 = process(arr,index + 1,rest);
        int p2 = 0;
        if(arr[index] <= rest){
            p2 = arr[index] + process(arr,index + 1,rest - arr[index]);
        }
        return Math.max(p1,p2);
    }

    public static int dp(int[] arr){
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        int[][] dp = new int[arr.length + 1][sum/2 + 1];
        for (int i = arr.length - 1; i >= 0 ; i--) {
            for (int j = 0; j <= sum/2; j++) {
                int p1 = dp[i + 1][j];
                int p2 = 0;
                if(arr[i] <= j){
                    p2 = arr[i] + dp[i + 1][j - arr[i]];
                }
                dp[i][j] = Math.max(p1,p2);
            }
        }
        return dp[0][sum / 2];
    }

    public static int[] randomArray(int len, int value) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * value);
        }
        return arr;
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue = 50;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * maxLen);
            int[] arr = randomArray(len, maxValue);
            int ans1 = getSum(arr);
            int ans2 = dp(arr);
            if (ans1 != ans2) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }
}
